package summary;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/12 16:22
 */
public class Title1462II {

    public static List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        int[][] arr = new int[numCourses][numCourses];
        int[] inDegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            arr[pre[0]][pre[1]] = 1;
            inDegree[pre[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer poll = queue.poll();
                for (int j = 0; j < numCourses; j++) {
                    //poll -> j
                    if (arr[poll][j] == 1) {
                        // k - > poll    k -> j
                        for (int k = 0; k < numCourses; k++) {
                            if (arr[k][poll] == 1) {
                                arr[k][j] = 1;
                            }
                        }
                        inDegree[j]--;
                        if (inDegree[j] == 0) {
                            queue.offer(j);
                        }
                    }
                }
            }
        }
        List<Boolean> list = new ArrayList<>();
        for (int[] query : queries) {
            list.add(arr[query[0]][query[1]] == 1);
        }
        return list;
    }

    public static void main(String[] args) {
        int n = 5;
        int arr[][] = {{4, 3}, {4, 1}, {4, 0}, {3, 2}, {3, 1}, {3, 0}, {2, 1}, {2, 0}, {1, 0}};
        int[][] arr1 = {{1, 4}, {4, 2}, {0, 1}, {4, 0}, {0, 2}, {1, 3}, {0, 1}};
        checkIfPrerequisite(n, arr, arr1);
    }
}
